package jjk.astar
{
	
	import jjk.model.Grid;
	import jjk.model.Node;

	public class Astar
	{
		public var startNode:Node;
		public var endNode:Node;
		
		private var openNodes:Array;//开启的列表
		private var closedNodes:Array;//关闭的列表
		private var _pathNodes:Array;
		
		private var straightCost:int = 10;//直接的开销
		private var diagonalCost:int = 14;//对角线的开销
		
		private var _pathType:int = 8;
		
		//八个方向寻路
		public static const TYPE_PATH_EIGHT:int = 8;
		//四个方向寻路,对角线不能走
		public static const TYPE_PATH_FOUR:int = 4;
		
		private var grid:Grid = null;
		
		public function Astar()
		{
		}
		
		public function get pathType():int
		{
			return _pathType;
		}

		public function set pathType(value:int):void
		{
			_pathType = value;
		}

		public function get pathNodes():Array
		{
			return _pathNodes;
		}

		public function set pathNodes(value:Array):void
		{
			_pathNodes = value;
		}

		 /**
		 * 查找路径
		 * 
		 * 
		 * 
		 * */
		public function findPath(grid:Grid):Boolean
		{
			this.grid = grid;
			
			openNodes = [];
			closedNodes = [];
			
			
			return search();
			
			
		}
		
		
		private function search():Boolean
		{
			
			var tempNode:Node = startNode;
			
			
			while(tempNode != endNode)
			{
				var startX:int = Math.max(tempNode.x-1,0);
				var endX:int = Math.min(tempNode.x+1,grid.cols-1);
				
				var startY:int = Math.max(tempNode.y-1,0);
				var endY:int = Math.min(tempNode.y+1,grid.rows-1);
				
				
				var g1:int = tempNode.g;
				
				for(var x:int=startX;x<=endX;x++)
				{
					for(var y:int=startY;y<=endY;y++)
					{
						var testNode:Node = grid.getNode(x,y);
						
						if(testNode == tempNode || !testNode.crossable||inClosed(testNode))
						{
							continue;
						}
						
						
						if(_pathType == TYPE_PATH_FOUR)
						{
							if(testNode.x!=tempNode.x && testNode.y!=tempNode.y)
							{
								continue;
							}
						}
						
						var cost:int = straightCost;
						if(testNode.x!=tempNode.x && testNode.y!=tempNode.y)
						{
							cost = diagonalCost;
						}
						
						var g:int = cost + g1;
						var h:int = manhattan(testNode);
						var f:int = g + h;
						
						//在开放列表中
						if(inOpen(testNode))
						{
							if(f<testNode.f)
							{
								testNode.h = h;
								testNode.g = g;
								testNode.f = f;
								testNode.parent = tempNode;
							}
						}
						else
						{
							testNode.h = h;
							testNode.g = g;
							testNode.f = f;
							testNode.parent = tempNode;
							openNodes.push(testNode);
						}
					}
				}
				
				closedNodes.push(tempNode);
				
				if(openNodes.length==0)
				{
					trace("没有找出路径");
					return false;
				}
				
				openNodes.sortOn("f",Array.NUMERIC);
				
//				trace("--------------------------------------");
//				tempNode.toString();
//				trace("--------------------------------------");
				tempNode = openNodes.shift() as Node;
				
			}
			buildPath();
			
			
			return true;	
		}
		
		private function buildPath():void
		{
			_pathNodes = new Array();
			var node:Node = endNode;
			_pathNodes.push(node);
			while(node != startNode)
			{
					node = node.parent;
					_pathNodes.unshift(node);
			}
			
		}
		
		
		/**
		 * 曼哈顿估算法，计算H值
		 */ 
		private function manhattan(node:Node):int
		{
			return Math.abs(endNode.x - node.x)*straightCost + Math.abs(endNode.y - node.y)*straightCost;	
		}
		
		/**
		 * 是否在开放列表中
		 * 
		 */ 
		private function inOpen(node:Node):Boolean
		{
			for(var i:int=0;i<openNodes.length;i++)
			{
				if(openNodes[i] == node)
				{
					return true;
				}
			}
			return false;
		}
		
		/**
		 * 是否在关闭列表中
		 */ 
		private function inClosed(node:Node):Boolean
		{
			for(var i:int=0;i<closedNodes.length;i++)
			{
				if(closedNodes[i] == node)
				{
					return true;
				}
			}
			return false;
		}
	}
}